1. Field of the Invention
The present invention relates to the field of computer controlled graphics display systems. More specifically, the present invention relates to a method and system for real time illumination of computer generated images.
2. Background Art
With the advent of graphics based operating systems, graphical user interfaces have become the dominant mode of interacting with computers. Such a progress was made possible due in large part to the innovations in computer graphics. Computer graphics, in a practical sense, concerns the representation of real or imaginary objects based on their computer-based models for interaction with computer users.
In the evolution of computer graphics, rendering a realistic image of a real or imaginary object has been a prime goal for researchers and users alike. At the cutting edge in this quest for realism in computer graphics lies three dimensional (3D) graphics systems. However, rendering realistic 3D images in a graphics system has been slow in coming because it requires enormous and costly computing resources.
One of the most important factors in rendering realistic 3D graphics images is shading. Specifically, rendering realistic 3D graphics requires accurate and efficient modeling of 3D surfaces based upon the position, orientation, and characteristics of the surfaces and the light sources illuminating them. In computer graphics, illumination or lighting model refers to factors determining a surface's color at a given point, usually a pixel, and is typically represented by a lighting equation. Shading, on the other hand, refers to systematic utilization of the illumination or lighting model to render an image. Well known lighting and shading models are discussed in detail in Computer Graphics: Principles and Practice by James D. Foley, et al., Addison-Wesley (1996).
In order to produce realistically shaded 3D images in computer graphics systems, the interaction between lights and surface must be modeled for replication. However, due to complexities of such interactions which are based on rules of optics and thermal dynamics, traditional modeling has been based largely on approximations and simplifications. To this date, two shading methods have been popular with computer graphics professionals.
In 1971, Gouraud first proposed a shading method ("Gouraud shading") using intensity interpolation. Under Gouraud shading, intensity is determined at each vertex of a polygon, typically a triangle. Then, each polygon is shaded by linear interpolation of vertex intensities along each edge and then between edges. However, since this method did not determine intensities at individual pixels, it did not provide realistic shading of images.
A few years later, Phong Bui-Tuong proposed a shading method for determining colors at each individual pixel. He formulated a lighting model derived largely from empirical observations. Bui-Tuong, Phong, "Illumination for Computer Generated Pictures," CACM, 18(6), June 1975, 311-317. The original Phong model used a reflection vector to compute the position and extent of specular highlights on objects. J. Blinn simplified the Phong equation by using a half-angle vector between the light vector and the eye vector. In both cases, 3D surfaces were shaded by computing a color value at each pixel. Hence, Phong shading was more accurate and realistic than Gouraud shading. At the same time Phong shading was more difficult to implement because it required far more computer graphics resources than Gouraud shading.
A modified Phong lighting equation ("modified Phong lighting equation"), incorporating color wavelength dependent components and the half-angle vector, computes the color (i.e., intensity) of a pixel according to the following formulation: EQU I.sub..lambda. =I.sub.a.lambda. k.sub.a O.sub.a.lambda. +f.sub.att I.sub.p.lambda. [k.sub.d O.sub.d.lambda. (N.cndot.L)+k.sub.s O.sub.s.lambda. (N.cndot.H).sup.n ]
where,
I.sub..lambda. =Intensity or color of a light at a pixel; PA1 I.sub.a.lambda. =Intensity of ambient light; PA1 k.sub.a =Ambient-reflection coefficient with range between 0 to 1; PA1 O.sub.a.lambda. =Object's ambient color; PA1 f.sub.att =Light source attenuation factor; PA1 I.sub.p.lambda. =point light source intensity; PA1 k.sub.d =Material's diffuse-reflection coefficient (a constant with a value between 0 and 1); PA1 O.sub.d.lambda. =Object's diffuse color; PA1 k.sub.s =Material's specular-reflection coefficient set as a constant between 0 and 1; PA1 O.sub.s.lambda. =Object's specular color; PA1 n=specular exponent (i.e., shininess of the material); PA1 N=surface normal vector at the pixel; PA1 L=light-source vector (pointing from pixel to light) at the pixel; and PA1 H=half-angle vector between light-source vector and eye vector at the pixel. PA1 C=color of the pixel, PA1 Sa=ambient color of the scene, PA1 Attn=attenuation of light intensity due to distance (local and spot lights), PA1 Ca=ambient color of light*ambient color of material, PA1 Cd=diffuse color of light*diffuse color of material, PA1 Cs=specular color of light*specular color of material, PA1 s=specular exponent (i.e., shininess of the material), PA1 N=surface normal vector at the pixel, PA1 L=light-source vector (pointing from pixel to light) at the pixel, and PA1 H=half-angle vector between light-source vector and eye vector at the pixel.
Another variation of the Phong lighting equation is the Phong-Blinn equation ("Phong-Blinn lighting equation"). This equation computes the color (i.e., intensity) of a pixel according to the following formulation: EQU C=Sa+Attn.times.(Ca+Cd.times.(N.cndot.L)+Cs.times.(N.cndot.H).sup.s)
where,
Although the modified Phong lighting equation and the Phong-Blinn equation (hereinafter collectively referred to as "Phong lighting equation") differ in some aspects, they produce similar lighting values. The implementation of the Phong lighting equation requires considerable computing resources to evaluate due mainly to the two dot product terms N.cndot.L and (N.cndot.H).sup.s. The dot product N.cndot.L is a diffuse term which accounts for reflection of light from dull surfaces. Specular term, represented by (N.cndot.H).sup.s, accounts for reflection of light from shiny surfaces as in a highlight off a shiny surface. The dot product N.cndot.H is part of the specular term.
The relationship between the vectors, N, L, and H are illustrated in Prior Art FIG. 1. Vector L is a light direction vector pointing from a point P on a 3D surface 100 to a light source, such as a lamp. Vector N is a surface normal vector at point P. Eye vector is a vector pointing from point P to a viewer's eye. Vector H is a half-angle vector bisecting the light vector L and the eye vector. Vector R is a reflection vector that was used in determining a specular term in the original Phong lighting equation.
In the Phong shading method, the N vector at a point (i.e. pixel) is typically interpolated between the three vertices of a triangle. The light vector L and the half-angle vector H at a given pixel are constant over a triangle for lights and viewer at infinity. However, for local lights, the L vector at the pixel is also interpolated in a similar manner. Likewise, for a local viewer, the H vector at the pixel is similarly interpolated. Hence, at a given pixel, for a local light and a local viewer, all three vectors N, L, and H are linearly interpolated based on the N, L, and H vectors of the vertices of a polygon. In an exemplary triangle, linear interpolation of N, L, and H vectors at a given pixel would involve 9 vectors: three vectors N, L, and H at each of the three vertices.
The linear interpolation of N, L, and H vectors at a given pixel yields vectors whose orientations (i.e. directions) are accurate interpolations, but whose lengths (i.e. magnitudes) depart from the interpolation scheme. Hence, the interpolated vectors N, L, and H must be normalized before being used in the Phong equation above. The normalization involves an inverse square-root operation. After normalization, the diffuse term is computed by evaluating the dot product N.cndot.L. The specular term is determined by evaluating the dot product N.cndot.H raised to a power s. The diffuse and specular terms are then used in the above equation along with the other well known variables to produce a color at a given pixel.
These remaining variables and the method of determining their values are well known in the art and have been routinely implemented without undue difficulty in graphics systems. Those desiring further information on the Phong lighting equation and related variables are referred to Computer Graphics: Principles and Practice by James D. Foley, et al., Addison-Wesley (1996), 772-731, ISBN 0-201-84840-6, which is incorporated herein by reference as a part of this background material.
All these vector and dot product calculations translate into extensive and costly hardware resources. Moreover, in order to calculate the dot products, all three vectors, N, L, and H must be determined at every single pixel corresponding to a point on a surface and then normalized by brute force method. Given that even the low-end color monitors of today have more than half-a-million pixels, which are comprised of three sub-pixels in turn, the Phong lighting equation becomes prohibitively costly and slow to implement in computer graphics systems.
Recognizing the costly nature of the brute force approach, several methods have been devised to implement the Phong lighting equation in a more efficient way in terms of cost, hardware, and speed. In one case, Kuijk and Blake used angular interpolation. A. A. M Kuijk & E. H. Blake, Faster Shading via Angular Interpolation, Comp. Graphics Forum 8 (1989), 315-324. In another case, Claussen used two approaches: one without re-normalization of surface normal vector, and the other with re-normalization of surface normal vector. Ute Claussen, Real Time Phong Shading, Proceedings of the Eurographics 90, 29-36. However, Claussen method applied the Phong equation directly without any reduction. In both cases, the hardware costs were still high and resulting shading sacrificed realism for speed, cost, and simplicity.
In contrast, Bishop and Weimer used a novel approach of converting the entire Phong equation to a second degree Taylor expansion and then using forward differences to evaluate the equation at each pixel. Bishop, G. & Weimer, D. M., Fast Phong Shading, Proceedings of SIGGRAPH, 1986, 103-106. However, this method still entailed a high setup cost in computing the coefficients of the Taylor series. Further, it proved suitable only for iterative scan line renderers where forward differences could be implemented. Hence, graphics system designers were faced with expensive, slow but highly realistic shading effects or cheap, fast graphics system with shading effects falling short on realism.
Thus, what is needed is a computer graphics system and method that implement the Phong lighting model for shading 3D images more efficiently at each pixel while retaining close approximation to the Phong lighting equation. What is further needed is a system and method that reduce resource intensive calculations involved in normalization and the dot product computations. It is preferable if such a system and method for shading 3D images allow hardware implementation of the Phong lighting method.
Accordingly, the present invention provides a solution whereby computer controlled graphics display systems and methods for shading a 3D image efficiently and closely approximates Phong shading in real time. The present invention reduces resource intensive normalization and dot product computations involved in the Phong lighting model. Furthermore, the present invention provides a computer controlled graphics display systems and methods for shading a 3D image that implement the Phong lighting model in hardware.